package stack_and_queue;

import java.util.Deque;
import java.util.LinkedList;

public class 望远镜中最高的海拔  {
    class Solution {
        public int[] maxAltitude(int[] heights, int limit) {
            if(heights.length == 0 || limit == 0) return new int[0];
            Deque<Integer> deque = new LinkedList<>();
            int[] res = new int[heights.length - limit + 1];
            for(int j = 0, i = 1 - limit; j < heights.length; i++, j++) {
                // 删除 deque 中对应的 heights[i-1]
                if(i > 0 && deque.peekFirst() == heights[i - 1])
                    deque.removeFirst();
                // 保持 deque 递减
                while(!deque.isEmpty() && deque.peekLast() < heights[j])
                    deque.removeLast();
                deque.addLast(heights[j]);
                // 记录窗口最大值
                if(i >= 0)
                    res[i] = deque.peekFirst();
            }
            return res;
        }
    }
    class Solution2 {
        public int[] maxAltitude(int[] heights, int limit) {
            if(heights.length == 0 || limit == 0) return new int[0];
            Deque<Integer> deque = new LinkedList<>();
            int[] res = new int[heights.length - limit + 1];
            // 未形成窗口
            for(int i = 0; i < limit; i++) {
                while(!deque.isEmpty() && deque.peekLast() < heights[i])
                    deque.removeLast();
                deque.addLast(heights[i]);
            }
            res[0] = deque.peekFirst();
            // 形成窗口后
            for(int i = limit; i < heights.length; i++) {
                if(deque.peekFirst() == heights[i - limit])
                    deque.removeFirst();
                while(!deque.isEmpty() && deque.peekLast() < heights[i])
                    deque.removeLast();
                deque.addLast(heights[i]);
                res[i - limit + 1] = deque.peekFirst();
            }
            return res;
        }
    }
}
